// @algorithm @lc id=2090 lang=cpp 
// @title number-of-ways-to-arrive-at-destination
// 「记忆化搜索」对应着「深度优先搜索」求解拓扑排序
// 「动态规划」对应着「广度优先搜索」求解拓扑排序


// #define print(...)
// @test(7,[[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]])=4
// @test(2,[[1,0,10]])=1
class Solution {
public:
    int countPaths(int n, vector<vector<int>>& roads) {
        const int mod = 1000'000'000 + 7;
        vector<vector<long long>> path(n, vector<long long>(n, LLONG_MAX/2)); // 路网
        for(auto & way : roads)
            path[way[0]][way[1]] = path[way[1]][way[0]] = way[2];
        for(int i=0; i<n; i++)
            path[i][i] = 0;
        vector<bool> passed(n, false); // Dijkstra算法求(0到各点)单源最短路径
        auto & to = path[0]; // path[0][ ]: 从 Zero 到各点的距离
        int c = n;
        while(c--){
            int j = -1;
            for(int i=0; i<n; i++){
                if(passed[i]) continue;
                if(-1 ==j || to[i] < to[j])
                    j = i;
            }
            passed[j] = true;
            for(int x=0; x<n; x++)
                to[x] = min(to[x], to[j]+path[j][x]);
        }

        vector<vector<int>> G(n); // (从0出发)构造有向图
        for(auto & way : roads){
            auto near = way[to[way[0]] < to[way[1]] ? 0 : 1],
                far = -near+way[0]+way[1];
            if(to[near] + way[2] == to[far]) // 搜集最短路径上的点
                G[near].push_back(far);
        }

        vector<int> from(n, 0); // 记忆化搜索有向图上到达n-1的路径数
        function<int(int)> dfs = [&](int src)->int{
            if(src == n-1) return 1;
            if(from[src]) return from[src];
            for(auto far : G[src]){
                from[src] += dfs(far);
                if(from[src] >= mod)
                    from[src] -= mod;
            }
            return from[src];
        };
        return dfs(0);
    }
};